#include <cstdio>
#define MAX_V 20001


class No{
	public:
	No(int x){v=x;next=NULL;}
	int v;
	No *next;
};

class Lista{
	public:
	Lista(){inicio=fim=NULL;grau=0;}
	
	No* inicio;
	No* fim;
	int grau;
	void inserir(int x);
	void esvasiar();
};
void Lista::esvasiar(){
	No *temp;
	while(inicio){
		temp=inicio->next;
		delete inicio;
		inicio = NULL;
		inicio=temp;
	}
	grau=0;
}

void Lista::inserir(int x){
	grau++;
	No *n = new No(x);
	if(inicio==NULL){
		inicio=fim=n;
	}
	else{
		fim->next = n;
		fim = n;
	}
}

Lista l[MAX_V];
int N, M, i, a, b, gm, im;
int cor[MAX_V], tot;

void read(){
	gm=0;
	for(i=1;i<=N;i++){
		cor[i]=0;
		l[i].esvasiar();
	}
	for(i=0;i<M;i++){
		scanf("%d %d", &a, &b);
		l[a].inserir(b);
		if(l[a].grau>gm){gm=l[a].grau;im=a;}
		l[b].inserir(a);
		if(l[b].grau>gm){gm=l[b].grau;im=b;}
	}
}
bool np[MAX_V];//cores q nao pode
void colorir(int x){
	if(cor[x]==0){
		No *n=l[x].inicio;
		{
			for(i=1;i<=N;i++){np[i]=false;}
			while(n){
				np[cor[n->v]]=true;
				n=n->next;
			}
			for(i=1;i<=tot&&np[i];i++);
			if(i>tot)tot++;
		}
		cor[x]=i;
		
		n=l[x].inicio;
		while(n){
			colorir(n->v);
			n=n->next;
		}
		
	}
}

void process(){
	tot=1;
	colorir(im);
	for(int f=1;f<=N;f++)if(cor[f]==0)colorir(f);
}
int main(){
	freopen("L4Q2.in","r",stdin);
	freopen("L4Q2.out","w",stdout);
	int z=1;
	while(scanf("%d %d", &N, &M)==2){
		read();
		process();
		printf("Conjunto #%d\n%d\n", z++,M, tot);
		
	}
	
}
